package weekMatch.one_341;

import com.sun.org.apache.xpath.internal.operations.Or;

import java.util.*;

public class LeeCode_04_failed {
    public static void main(String[] args) {
//        System.out.println(minimumTotalPrice(4, new int[][]{{0, 1}, {1, 2}, {1, 3}}, new int[]{2, 2, 10, 6}, new int[][]{{0, 3}, {2, 1}, {2, 3}}));
//        System.out.println(minimumTotalPrice(5, new int[][]{{2, 0}, {3, 1}, {1, 0}, {0, 4}},
//                new int[]{2, 16, 4, 16, 6}, new int[][]{{4, 3}}));
        System.out.println(minimumTotalPrice(2, new int[][]{{0, 1}},
                new int[]{2, 2}, new int[][]{{0, 0}}));

    }
    private static int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        int[] copyP = Arrays.copyOf(price, price.length);
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n];
            Arrays.fill(dp[i], 1000_000);
        }
        int[][] dp2 = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp2[i] = new int[n];
            Arrays.fill(dp2[i], 1000_000);
        }
        Set<String> close = new HashSet<>();
        Set<Integer> fob = new HashSet<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < price.length; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
            close.add(edge[0] + "," + edge[1]);
            close.add(edge[1] + "," + edge[0]);
        }
        boolean[] changed = new boolean[price.length];
        for (int i = 0; i < price.length; i++) {
            for (int j = i; j < price.length; j++) {
                String key = i + "," + j;
                if (close.contains(key)) {
                    continue;
                }
                if (!changed[i] && !fob.contains(i)){
                    price[i] /= 2;
                    changed[i] = true;
                }
                if (!changed[j] && !fob.contains(j)){
                    price[j] /= 2;
                    changed[j] = true;
                }
                List<Integer> li = map.get(i);
                List<Integer> lj = map.get(j);
                fob.addAll(li);
                fob.addAll(lj);
            }
        }
        int[] price2 = new int[price.length];
        for (int i = 0; i < changed.length; i++) {
            if (!changed[i]){
                price2[i] = copyP[i] / 2;
            }else {
                price2[i] = copyP[i];
            }
        }
        return Math.min(search(n, edges, price, trips, dp), search(n, edges, price2, trips, dp2));
    }

    private static int search(int n, int[][] edges, int[] price, int[][] trips, int[][] dp) {
        for (int i = 0; i < price.length; i++) {
            dp[i][i] = price[i];
        }
        for (int[] edge : edges) {
            dp[edge[0]][edge[1]] = price[edge[0]] + price[edge[1]];
            dp[edge[1]][edge[0]] = price[edge[0]] + price[edge[1]];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] > dp[i][k] + dp[k][j] - dp[k][k]){
                        dp[i][j] = dp[i][k] + dp[k][j] - dp[k][k];
                    }
                }
            }
        }
        int ans = 0;
        for (int[] trip : trips) {
            if (trip[0] == trip[1]){
                ans += dp[trip[0]][trip[1]];
                continue;
            }
            ans += dp[trip[0]][trip[1]];
        }
        return ans;
    }
}
